#!/usr/bin/python
#-*- coding:utf-8 -*-
# Description:  华容道问题求解.
#               8代表空格，从0开始（一般游戏从1开始）
#        
#        
#  
################################################################
import numpy as np
from pprint import pprint
from collections import deque, namedtuple
import sys
sys.setrecursionlimit(100000)

class square(object):
    '华容道方格'
    def __init__(self, v = None):
        if isinstance(v, np.ndarray):
            self.v = v
        else:
            self.v = np.arange(9, dtype=int)

    def shuffle(self):
        np.random.shuffle(self.v)
            
    def label(self):
        '唯一数字标识'
        return reduce(lambda x, y: x*9 + y, self.v)

    def ind(self):
        return np.where(self.v == 8)[0][0]

    def up(self):
        i = self.ind()
        if i > 2 :
            t = self.v.copy()
            t[i], t[i-3] = self.v[i-3], 8
            return square(t)
        else :
            return None

    def down(self):
        i = self.ind()
        if i < 6 :
            t = self.v.copy()
            t[i], t[i+3] = self.v[i+3], 8
            return square(t)
        else :
            return None

    def left(self):
        i = self.ind()
        if i % 3 > 0 :
            t = self.v.copy()
            t[i], t[i-1] = self.v[i-1], 8
            return square(t)
        else :
            return None

    def right(self):
        i = self.ind()
        if i % 3 < 2 :
            t = self.v.copy()
            t[i], t[i+1] = self.v[i+1], 8
            return square(t)
        else :
            return None

        
    def __str__(self):
        return str(self.v.reshape(3,3))

flag = np.zeros(9**9, bool) # 已经访问过了

direction = [ 'up', 'down', 'left', 'right']

path = []

target = 6053444
dbg_num = 0
def search(start):
    'start: 起始方格状态'
    global dbg_num, path, flag
    dbg_num +=1
    #if dbg_num > 100 : sys.exit()
    #print 'label =', start.label()
    #print start
    flag[start.label()] = True
    if start.label() == target:
        path.append(start)
        return True
    else:
        for d in direction:
            if d == 'up': nxt = start.up()
            elif d == 'down': nxt = start.down()
            elif d == 'left': nxt = start.left()
            elif d == 'right': nxt = start.right()
            if nxt != None and not flag[nxt.label()]:
                if search(nxt) :
                    path.append(start)
                    return True
        return False #没有找到
                

if __name__ == '__main__':
    a = square()
    a.shuffle()
    print a
    print '--------------down'
    print a.down()
    print '--------------up'
    print a.up()
    print '--------------left'
    print a.left()
    print '--------------right'
    print a.right()
    print '='*80
    t = np.array([0,1,2,3,8,4,6,7,5], dtype=int)
    start = square(t)
    #start.shuffle()
    if search(start):
        print "==========Got it:"
        for i in reversed(path): print i
    else :
        print "Can't finished!"
